package binary_tree.LeetCode;

/**
 * 根据先序遍历和中序遍历构建额二叉树并且返回根节点
 */
public class Num105 {
    //表示当前处理到了前序遍历的元素位置
    private int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       return buildTreeHelp(preorder,inorder,0,inorder.length-1);
    }

    /**
     * 从前序遍历中取出树根值，借助中序遍历[left,right)还原二叉树，返回二叉树的根节点
     * @param preorder
     * @param inorder
     * @param left
     * @param right
     * @return
     */
    private TreeNode buildTreeHelp(int[] preorder, int[] inorder, int left, int right) {
        if (left>right){
            //此时就是个空区间
            return null;
        }
        if(index== preorder.length){
            //此时前序遍历的元素已经全部处理完毕
            return null;
        }
        //先从前序遍历中找出当前二叉树的根节点
        TreeNode root=new TreeNode(preorder[index]);
        index++;
        //处理左子树，先找出根节点在中序遍历中的位置
        int p=find(root.val,inorder);
        root.left=buildTreeHelp(preorder,inorder,left,p-1);
        //处理右子树
        root.right=buildTreeHelp(preorder,inorder,p+1,right);
        return root;
    }

    /**
     * 在中序遍历中找到val对应位置的索引
     * @param val
     * @param inorder
     * @return
     */
    private int find(int val, int[] inorder) {
        for (int i = 0; i <inorder.length; i++) {
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }
}
